package com.xuwei.base.sort;
/**
 * 快速排序演示
 * @author David
 *
 */
public class QuickSort {

	public static void main(String[] args) {
		
		int arr[]={-6,-12,11,9,0,23,8,-1,24};
		//排序前
		System.out.println("排序前：");
		for(int i=0;i<arr.length;i++)
		{
			System.out.print(arr[i]+"  ");
		}
		
		//调用快速排序
		QuickSort.sort(arr,0,arr.length-1);
		
		//排序后
		System.out.println("\n排序后：");
		for(int i=0;i<arr.length;i++)
		{
			System.out.print(arr[i]+"  ");
		}

	}


	public static void sort(int[] array,int left,int right){
		 int l=left;
	     int r=right;
	     int pivot=array[l];
	 
		 while(l<r){
			while(l<r&&array[r]>=pivot)r--;
			
			if(l<r)
			{
			  array[l]=array[l]^array[r];
			  array[r]=array[l]^array[r];
			  array[l]=array[l]^array[r];
			  l++;		 
			}
			 
			while(l<r&&array[l]<=pivot)l++;
			 
			if(l<r){
			  array[l]=array[l]^array[r];
			  array[r]=array[l]^array[r];
			  array[l]=array[l]^array[r];
			  r--;		 
			}

		 }

		if(l>left)sort(array,left,r-1);
		if(r<right)sort(array,l+1,right);		 

	}
	
	
	
}
